package leetcode.sort;

import leetcode.util.CommonUtils;
import org.junit.Test;

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/23 9:56
 * @description :
 */
public class Review {

    int[] nums = {7, 8, 9, 10, 1, 2, 3, 5, 4, 6};

    @Test
    public void bubble_sort_test() {
        bubble_sort(nums);
        System.out.println("冒泡：" + Arrays.toString(nums));
    }

    public void bubble_sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    CommonUtils.charge(arr, j, j + 1);
                    flag = false;
                }
            }
            if (flag) break;
        }
    }

    @Test
    public void select_sort_test() {
        select_sort(nums);
        System.out.println("选择：" + Arrays.toString(nums));
    }

    public void select_sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }
            CommonUtils.charge(arr, i, minIndex);
        }
    }

    @Test
    public void insert_sort_test() {
        insert_sort(nums);
        System.out.println("插入：" + Arrays.toString(nums));
    }

    public void insert_sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertIndex = i - 1;
            int insertValue = arr[insertIndex + 1];
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i)
                arr[insertIndex + 1] = insertValue;
        }
    }

    @Test
    public void quick_sort_test() {
        quick_sort(nums, 0, nums.length - 1);
        System.out.println("快排：" + Arrays.toString(nums));
    }

    public void quick_sort(int[] arr, int left, int right) {
        if (left >= right) return;
        int l = left;
        int r = right;
        int pivot = arr[l];
        while (l < r) {
            while (l < r && arr[r] >= pivot) r--;
            arr[l] = arr[r];
            while (l < r && arr[l] <= pivot) l++;
            arr[r] = arr[l];
        }
        arr[l] = pivot;
        quick_sort(arr, left, l);
        quick_sort(arr, l + 1, right);
    }


    @Test
    public void heap_sort_test() {
        heap_sort(nums);
        System.out.println("堆排：" + Arrays.toString(nums));
    }

    /**
     * 构建大顶堆
     *
     * @param arr
     * @param parentIndex
     * @param len
     */
    public void adjust(int[] arr, int parentIndex, int len) {
        int temp = arr[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < len) {
            if (childIndex + 1 < len && arr[childIndex + 1] > arr[childIndex])
                childIndex++;
            if (arr[childIndex] <= temp) break;
            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }
        arr[parentIndex] = temp;
    }

    public void heap_sort(int[] arr) {
        //构建大顶堆
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            adjust(arr, i, arr.length);
        }
        //排序
        for (int i = arr.length - 1; i >= 0; i--) {
            CommonUtils.charge(arr, 0, i);
            adjust(arr, 0, i);
        }
    }

    @Test
    public void merge_sort_test() {
        merge_sort(nums, 0, nums.length - 1, new int[nums.length]);
        System.out.println("归并：" + Arrays.toString(nums));
    }

    public void merge_sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + right >> 1;
            merge_sort(arr, left, mid, temp);
            merge_sort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid || j <= right) {
            temp[t++] = (i <= mid ? arr[i] : Integer.MAX_VALUE)
                    < (j <= right ? arr[j] : Integer.MAX_VALUE)
                    ? arr[i++] : arr[j++];
        }
        int tempLeft = left;
        t = 0;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }
    }

    @Test
    public void lruCache_test() {
        LRUCache<Integer, Integer> lruCache = new LRUCache<>(3);
        lruCache.put(1, 2);
        lruCache.put(2, 2);
        lruCache.put(3, 2);
        lruCache.get(2);
        //必须这样测试
        //否则会报ConcurrentModificationException异常
        Iterator<Map.Entry<Integer, Integer>> it = lruCache.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry entry = it.next();
            System.out.println(entry.getKey() + "   " + entry.getValue());
        }
        lruCache.put(4, 3);
        lruCache.get(2);
        lruCache.put(4, 5);
        it = lruCache.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry entry = it.next();
            System.out.println(entry.getKey() + "   " + entry.getValue());
        }
    }

    class LRUCache<K, V> extends LinkedHashMap<K, V> {
        private final int CACHE_SIZE;

        public LRUCache(int cacheSizes) {
            super((int) Math.ceil(cacheSizes / 0.75f) + 1, 0.75f, true);
            this.CACHE_SIZE = cacheSizes;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > CACHE_SIZE;
        }
    }

    @Test
    public void printABC_test() throws InterruptedException {
        Data data = new Data();
        new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                data.printA();
            }
        }).start();
        new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                data.printB();
            }
        }).start();
        new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                data.printC();
            }
        }).start();
        TimeUnit.MILLISECONDS.sleep(200);
    }

    class Data {
        private int num = 1;
        ReentrantLock lock = new ReentrantLock();
        Condition conditionA = lock.newCondition();
        Condition conditionB = lock.newCondition();
        Condition conditionC = lock.newCondition();

        public void printA() {
            lock.lock();
            try {
                if (num != 1) {
                    conditionA.await();
                }
                System.out.print('A');
                num = 2;
                conditionB.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }

        public void printB() {
            lock.lock();
            try {
                if (num != 2) {
                    conditionB.await();
                }
                System.out.print('B');
                num = 3;
                conditionC.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }

        public void printC() {
            lock.lock();
            try {
                if (num != 3) {
                    conditionC.await();
                }
                System.out.println('C');
                num = 1;
                conditionA.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }
    }


}
